package org.example.code.test2024.nine_mouth;

import java.util.ArrayList;
import java.util.List;

public class test0909 {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        for(int num : nums){
            int size = res.size();
            for(int i = 0; i < size; i++){
                List<Integer> temp = new ArrayList<Integer>(res.get(i));
                temp.add(num);
                res.add(temp);
            }
        }
        return res;
    }

    List<String> res = new ArrayList<>();
    char []a = {'2','3','4','5','6','7','8','9'};
    char [][]b={{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()){
            return res;
        }
        char[] charArray = digits.toCharArray();
        List<char[]> chars = new ArrayList<>();
        for(char c:charArray){
            for(int i=0;i<a.length;i++){
                if(a[i]==c){
                    chars.add(b[i]);
                    continue;
                }
            }
        }
        for(int i=0;i<chars.get(0).length;i++){
            fun(String.valueOf(chars.get(0)[i]),chars,1);
        }
        return res;
    }

    private void fun(String s, List<char[]> chars, int x) {
        if(x==chars.size()||s.length()==chars.size()){
//            System.out.println(s);
            res.add(s);
            return;
        }
        for(int i=0;i<chars.get(x).length;i++){
            String c = String.valueOf(chars.get(x)[i]);
            fun(s+c,chars,x+1);
        }
    }

    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        for(int i=0;i<candidates.length;i++){
            List<Integer> list = new ArrayList<>();
            list.add(candidates[i]);
            fun2(list,target-candidates[i],candidates,i);
        }
        return ans;
    }

    private void fun2(List<Integer> list, int t, int[] candidates,int i) {
        if(t==0){
            List<Integer> in = new ArrayList<>(list);
            ans.add(in);
            return;
        }
        for (int j=i;j<candidates.length;j++) {
            if (t >= candidates[j]) {
                list.add(candidates[j]);
                fun2(list, t - candidates[j], candidates,j);
//                list.removeLast();
            }
        }
    }

    public List<String> generateParenthesis(int n) {
        List<String> sum = new ArrayList<>();
        if(n==0){
            return sum;
        }
        fun3(sum,"",n,n);
        return sum;
    }

    private void fun3(List<String> sum, String s, int l, int r) {
        if(l==0&&r==0){
            sum.add(s);
            return;
        }
        if(l>0){
            fun3(sum,s+"(",l-1,r);
        }
        if(r>l){
            fun3(sum,s+")",l,r-1);
        }
    }

    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;
        boolean[][] visited = new boolean[n][m];
        char[] charArray = word.toCharArray();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]==charArray[0]){
                    visited[i][j] = true;
                    if(fun4(board,i,j,visited,charArray,1)){
                       return true;
                    }
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }

    int[] aa = {0,0,-1,1};
    int[] bb = {-1,1,0,0};
    private boolean fun4(char[][] board,int x, int y, boolean[][] visited, char[] charArray,int k) {
        if(k==charArray.length){
            return true;
        }
        for(int i=0;i<4;i++){
            int xx = x+aa[i];
            int yy = y+bb[i];
            if(xx<visited.length&&xx>=0&&yy<visited[0].length&&yy>=0&&!visited[xx][yy]&&k<charArray.length){
                if(board[xx][yy]==charArray[k]){
                    visited[xx][yy] = true;
                    if(fun4(board,xx,yy,visited,charArray,k+1)){
                        return true;
                    }
                    visited[xx][yy] = false;
                }
            }
        }
        return false;
    }

    public int searchInsert(int[] nums, int target) {
        if(nums.length==0){
            return 0;
        }
        if(nums[0]>target){
            return 0;
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target){
                return i;
            }
            if(nums[i]<target&&i+1<nums.length&&nums[i+1]>target){
                return i+1;
            }
        }
        return nums.length;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int n = 0,m = matrix[0].length-1;
        for(int i=0;i<matrix.length;i++){
            if(matrix[i][0]==target||matrix[i][m]==target){
                return true;
            }
            System.out.println(matrix[i][0]+"   "+matrix[i][m]);
            if(matrix[i][0]<target&&matrix[i][m]>target){
                n=i;
            }
        }
        System.out.println(n);
        for(int i=0;i<matrix[0].length;i++){
            if(matrix[n][i]==target){
                System.out.println(matrix[n][i]);
                return true;
            }
        }
        return false;
    }

    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        boolean flag = false;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target){
                if(flag){
                    res[1] = i;
                }else{
                    flag=true;
                    res[0]=i;
                    res[1]=i;
                }
            }
        }
        if(!flag){
            res[0]=-1;
            res[1]=-1;
        }
        return res;
    }

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 如果找到目标值，直接返回索引
            if (nums[mid] == target) {
                return mid;
            }

            // 判断哪一部分是有序的
            if (nums[left] <= nums[mid]) {
                // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;  // 目标值在左半部分
                } else {
                    left = mid + 1;   // 目标值在右半部分
                }
            } else {
                // 右半部分有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;   // 目标值在右半部分
                } else {
                    right = mid - 1;  // 目标值在左半部分
                }
            }
        }

        // 如果没找到，返回 -1
        return -1;
    }

    public int findMin(int[] nums) {
        int min = nums[0];
        for(int i=0;i<nums.length;i++){
            if(i+1<nums.length&&nums[i+1]<nums[i]){
                return nums[i+1];
            }
            Math.min(min,nums[i]);
        }
        return min;
    }



    public static void main(String[] args) {
        test0909 t = new test0909();
        int[] ints = t.searchRange(new int[]{1, 2, 3, 3, 4, 5}, 3);
        System.out.println(ints[0]+"    "+ints[1]);
    }
}
